class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        def matchBraket(begin, end):
            right = 1
            for i, c in enumerate(s[begin:end]):
                if c=='[': right+=1
                elif c==']': right-=1
                if right==0: return i+begin
            return end
        
        def decode(begin, end):
            if begin>=end: return ''

            if s[begin].isalpha():
                return s[begin]+decode(begin+1, end)
            
            acc = ''
            while s[begin].isdigit():
                acc += s[begin]
                begin+=1
            multi = int(acc)

            subBegin = begin+1
            subEnd = matchBraket(subBegin, end)
            return decode(subBegin, subEnd) * multi + decode(subEnd+1, end)
        
        return decode(0, len(s))

print(Solution().decodeString('2[abc]3[cd]ef'))